package 数据结构考纲.图;

import java.util.*;

public class MGraph {
    //邻接矩阵
    public final int[][] edge;
    public final String[] vex;   //顶点信息
    public final boolean[] visited;
    public final int vex_num;

    public final boolean is_direct;  //是否是有向图

    public MGraph(String[] vexs, int[][] edge, boolean is_direct) {
        this.edge = edge;   //邻接矩阵
        this.vex = vexs;
        this.visited = new boolean[edge.length];    //初始化访问数组
        this.vex_num = vexs.length;
        this.is_direct = is_direct;
    }

    //通过边来建立图   ["1"，"2", "123"]   原点、指向、权值
    public MGraph(String[][] edges, boolean is_direct) {    //是否是有向图
        Set<String> vex_set = new HashSet<>();
        for (String[] e : edges) {
            vex_set.add(e[0]);
            vex_set.add(e[1]);
        }
        //给顶点排序（按字母）
        this.vex = new String[vex_set.size()];
        int i = 0;
        for (String s : vex_set) {
            this.vex[i++] = s;
        }
        Arrays.sort(this.vex);
        //记录顶点对应下标，方便转化
        Map<String, Integer> map = new HashMap<>();
        for (i = 0; i < vex.length; i++) {
            map.put(this.vex[i], i);
        }
        //生成邻接矩阵
        this.edge = new int[vex.length][vex.length];
        for (String[] e : edges) {
            if (is_direct) {  //有向图
                this.edge[map.get(e[0])][map.get(e[1])] = Integer.parseInt(e[2]);
            } else {    //无向图
                this.edge[map.get(e[0])][map.get(e[1])] = Integer.parseInt(e[2]);
                this.edge[map.get(e[1])][map.get(e[0])] = Integer.parseInt(e[2]);
            }
        }
        //初始化访问数组
        this.visited = new boolean[vex.length];
        this.vex_num = vex.length;
        this.is_direct = is_direct;
    }

    //深度优先遍历
    public void DFSTraverse(String k) {
        for (int i = 0; i < vex.length; i++) {
            if (Objects.equals(vex[i], k)) {
                DFSTraverse(i);
                return;
            }
        }
        System.out.println("未找到该顶点，请核对数据");
    }

    public void DFSTraverse(int k) {
        Arrays.fill(visited, false);    //初始化访问数组
        DFS(k);
        for (int i = 0; i < edge.length; i++) {
            if (!visited[i])
                DFS(i);
        }
        System.out.println();
    }

    private void DFS(int k) {
        System.out.printf(this.vex[k] + ":" + k + "-> ");
        visited[k] = true;
        for (int i = 0; i < edge.length; i++) {
            if (edge[k][i] >= 1 && !visited[k]) {
                DFS(i);
            }
        }
    }

    //广度优先遍历
    public void BFSTraverse(String k) {
        for (int i = 0; i < vex.length; i++) {
            if (Objects.equals(vex[i], k)) {
                BFSTraverse(i);
                return;
            }
        }
        System.out.println("未找到该顶点，请核对数据");
    }

    public void BFSTraverse(int k) {
        Arrays.fill(visited, false);    //初始化访问数组
        BFS(k);
        for (int i = 0; i < edge.length; i++) {
            if (!visited[i])
                BFS(i);
        }
        System.out.println();

    }

    private void BFS(int k) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(k);
        while (!queue.isEmpty()) {
            int v = queue.poll();
            visited[v] = true;
            System.out.printf(this.vex[v] + ":" + v + "-> ");
            for (int i = 0; i < edge.length; i++) {
                if (edge[v][i] > 0 && !visited[i]) {
                    queue.add(i);
                    visited[i] = true;  //加入队列就要标记
                }
            }
        }
    }

    //Prim
    public void Prim(int k) {
        Arrays.fill(this.visited, false);
        int[] dis = new int[this.vex_num];  //其他节点到当前子树的最短距离
        int[] from = new int[this.vex_num];  //其他节点到当前子树的最短距离的源点
        this.visited[k] = true;

        //初始化距离
        for (int i = 0; i < vex_num; i++) {
            if (edge[k][i] > 0) {
                dis[i] = edge[k][i];
                from[i] = k;
            } else
                dis[i] = Integer.MAX_VALUE;
        }
        //边
        List<int[]> list = new ArrayList<>();    //MST边集合

        int count = 1;
        while (count < this.vex.length) {
            //找到最近未访问节点
            int min_dis = -1;
            for (int i = 0; i < vex_num; i++) {
                if (!visited[i]) {
                    if (min_dis == -1) {
                        min_dis = i;
                    } else {
                        if (dis[i] < dis[min_dis])
                            min_dis = i;
                    }
                }
            }
            if (min_dis == -1 || dis[min_dis] == Integer.MAX_VALUE) {
                System.out.println("找不到未访问过的最小节点，可能非联通图");
                return;
            }

            //加入该边
            list.add(new int[]{from[min_dis], min_dis, dis[min_dis]});
            visited[min_dis] = true;
            count++;

            //更新最短距离
            k = min_dis;    //更新当前源端
            for (int i = 0; i < vex_num; i++) {
                if (edge[k][i] > 0 && edge[k][i] < dis[i]) {
                    dis[i] = edge[k][i];
                    from[i] = k;
                }
            }
        }

        //处理数据
        MSTResultDisPlay(list);
    }

    //Kruskal
    public void Kruskal() {
        //对边集进行按照权值排序
        List<int[]> elist = new ArrayList<>();
        for (int i = 0; i < vex_num; i++) {
            for (int j = i + 1; j < vex_num; j++) {
                if (this.edge[i][j] > 0)
                    elist.add(new int[]{i, j, this.edge[i][j]});
            }
        }
        elist.sort((o1, o2) -> o1[2] - o2[2]);

        //选择最小且不不成环的边
        List<int[]> rlist = new ArrayList<>();  //记录每一趟的选择
        int e_count = 0;    //已选择的边数

        //每一个节点的初始子图都不同，改值相同的两个节点在同一个子图，故边两端的顶点不可在同一个紫图内，否则会成环
        //加入边时，要将边两边的子图更新到一个子图中，统一按边的源点的值，将值为目标点的子图值全部改为源点的子图值
        int[] sign = new int[vex_num];
        for (int i = 0; i < vex_num; i++) {
            sign[i] = i;
        }

        for (int[] e : elist) {
            if (sign[e[0]] != sign[e[1]]) {   //不成环,则加入
                rlist.add(e);
                e_count++;
                //更新子图值
                int t = sign[e[1]];
                for (int j = 0; j < vex_num; j++) {
                    if (sign[j] == t) {    //将值为目标点的子图值全部改为源点的子图值
                        sign[j] = sign[e[0]];
                    }
                }
            }
        }

        //分析结果
        if (e_count < vex_num - 1) {
            System.out.println("非联通图");
            return;
        }
        MSTResultDisPlay(rlist);
    }

    //MST结果输出
    private void MSTResultDisPlay(List<int[]> list) {
        int i = 1;
        int sum = 0;
        for (int[] e : list) {
            sum += e[2];
            System.out.printf("第%d趟: %s——%s 权值: %d\n", i++, this.vex[e[0]], this.vex[e[1]], e[2]);
        }
        System.out.println("该MST的权值和为: " + sum);
    }

    //Dijkstra  单源最短路径: 不可以有负值， 没有负全回路时仍可退出，但结果无用
    public void Dijkstra(int k) {
        int[] dis = new int[vex_num];   //源点到该节点的最短距离
        int[] path = new int[vex_num];  //该节点最短距离前驱
        Arrays.fill(this.visited, false);   //更新访问数组
        this.visited[k] = true;

        //更新源点到各顶点的距离
        for (int i = 0; i < vex_num; i++) {
            dis[i] = edge[k][i] == 0 ? Integer.MAX_VALUE : edge[k][i];
            path[i] = k;
        }
        dis[k] = 0;
        path[k] = k;

        //开始选择当前最近节点
        for (int c = 0; c < vex_num - 1; c++) {
            //找到未访问的最近节点
            int min_dis = -1;
            for (int i = 0; i < vex_num; i++) {
                if (!visited[i]) {
                    if (min_dis == -1) {
                        min_dis = i;
                    } else {
                        if (dis[i] < dis[min_dis])
                            min_dis = i;
                    }
                }
            }
            if (min_dis == -1)
                System.out.println("未找到未访问的最近节点");
            //将其置为已被访问
            visited[min_dis] = true;

            //更新最短距离
            for (int i = 0; i < vex_num; i++) {
                //未访问、边存在、距离更小
                if (!visited[i] && edge[min_dis][i] != 0 && dis[i] > dis[min_dis] + edge[min_dis][i]) {
                    path[i] = min_dis;
                    dis[i] = dis[min_dis] + edge[min_dis][i];
                }
            }
        }
        //输出访问情况
        outPath(dis, path, k);
    }

    //Floyd     多源最短路径: 可以有负权，不可有负权回路
    public void Floyd() {
        int[][] path = new int[vex_num][vex_num];   //path[i][j]: i访问j的前驱是path[i][j]
        int[][] dis = new int[vex_num][vex_num];
        //初始化
        for (int i = 0; i < vex_num; i++) {
            Arrays.fill(path[i], -1);
        }
        for (int i = 0; i < vex_num; i++) {
            for (int j = 0; j < vex_num; j++) {
                if (i != j && edge[i][j] == 0)
//                    dis[i][j] = Integer.MAX_VALUE;
                    dis[i][j] = Integer.MAX_VALUE / 2;
                else
                    dis[i][j] = edge[i][j];
            }
        }
        //floyd
        for (int k = 0; k < vex_num; k++) {
            for (int i = 0; i < vex_num; i++) {
                for (int j = 0; j < vex_num; j++) {
                    if (dis[i][j] > (long) dis[i][k] + dis[k][j]) {
                        dis[i][j] = dis[i][k] + dis[k][j];
                        path[i][j] = k;
                    }
                }
            }
        }
        //输出数据
        for (int i = 0; i < vex_num; i++) {
            for (int j = 0; j < vex_num; j++) {
                //i——>j的路径
                //这个输出路径还不好搞，要嵌套着来
                List<Integer> p = new ArrayList<>();
                Stack<Integer> stack = new Stack<>();
                stack.push(j);
                int v = i;  //当前顶点
                while (!stack.isEmpty()) {
                    int t = path[v][stack.peek()]; //当前前驱，若为-1则将当前节点加入路径，并将栈顶元素出栈为当前元素
                    if (t == -1) {
                        p.add(v);
                        v = stack.pop();
                    } else {
                        stack.push(t);
                    }
                }
                p.add(j);

                //输出路径
                System.out.print("长度为: " + dis[i][j]);
                System.out.print("  " + this.vex[i] + "-->" + this.vex[j] + ": ");
                for (int q = 0; q < p.size(); q++) {
                    System.out.printf("%s", vex[p.get(q)]);
                    if (q != p.size() - 1)
                        System.out.print("-> ");
                }
                System.out.println();
            }
        }

    }

    // 拓扑排序
    public boolean topologicalSort() {
        if (!is_direct) {
            System.out.print("无向图不可求拓扑排序");
            return false;
        }
        Stack<Integer> stack = new Stack<>();
        int[] degree = new int[vex_num];    //入度
        List<Integer> path = new ArrayList<>(vex_num);  //拓扑序列
        //初始化入度
        for (int i = 0; i < vex_num; i++) {
            //计算顶点i的入度
            for (int j = 0; j < vex_num; j++) {
                if (edge[j][i] > 0)
                    degree[i]++;
            }
        }
        //入度为0的顶点入栈
        for (int i = 0; i < vex_num; i++) {
            if (degree[i] == 0)
                stack.push(i);
        }

        while (!stack.isEmpty()) {
            int v = stack.pop();
            path.add(v);
            //更新其他顶点入度
            for (int i = 0; i < vex_num; i++) {
                if (edge[v][i] > 0) {
                    degree[i]--;
                    if (degree[i] == 0)
                        stack.push(i);
                }
            }
        }

        if (path.size() < vex_num) {
            System.out.println("图中有环");
            return false;
        }
        for (Integer v : path) {
            System.out.printf("%s ", vex[v]);
        }
        System.out.println();
        return true;

    }


    //Bellman-ford  单源最短路径(可带负权值，但不可以有源点可到达的负权回路，通过不断的松弛实现)
    public void bellmanFord(int k) {
        boolean updated = false;    //当前轮是否有更新操作
        int[] dis = new int[vex_num];   //距离数组
        int[] path = new int[vex_num];  //前驱数组
        //初始化 源点为0，其他点距离均为无穷
        Arrays.fill(dis, Integer.MAX_VALUE);
        Arrays.fill(path, k);
        dis[k] = 0;
        //遍历每条边，对其进行更新操作
        for (int c = 0; c < vex_num; c++) {
            updated = false;
            for (int i = 0; i < vex_num; i++) {
                for (int j = 0; j < vex_num; j++) {
                    if (edge[i][j] != 0) {//边要存在，但权值可以为负
                        //从i到j的距离比目前到j的方案更近，边的松弛操作
                        if ((long) dis[i] + edge[i][j] < dis[j]) {  //用long防止加法溢出
                            updated = true;
                            dis[j] = dis[i] + edge[i][j];
                            path[j] = i;
                        }
                    }
                }
            }
            if (!updated)
                break;
        }
        if (updated) {
            System.out.println("图中存在源点可到达的负环，无法求得单源最短路径");
            return;
        }
        outPath(dis, path, k);
    }

    //SPFA  单源最短路径（将Bellman-ford的松弛操作优化为队列中进行）
    public void SPFA(int k) {
        int[] dis = new int[vex_num];   //距离数组
        int[] path = new int[vex_num];  //前驱数组
        Queue<Integer> queue = new LinkedList<>();

        //初始化 源点为0，其他点距离均为无穷
        Arrays.fill(dis, Integer.MAX_VALUE);
        Arrays.fill(path, k);
        dis[k] = 0;
        queue.add(k);   //将源点入队
        Arrays.fill(visited, false);
        visited[k] = true;     //标记数组用来记录哪些顶点在队列中

        //遍历每条边，对其进行更新操作
        while (!queue.isEmpty()) {
            //取出队首节点，依次判断其邻边能否进行松弛操作
            int v = queue.poll();
            visited[v] = false;
            for (int i = 0; i < vex_num; i++) {
                if (edge[v][i] != 0) {
                    if (dis[i] > dis[v] + edge[v][i]) {
                        dis[i] = dis[v] + edge[v][i];
                        path[i] = v;
                        if (!visited[i]) {  //不在队列中则入队
                            queue.add(i);   //将可以松弛的边的邻接点入队
                            visited[i] = true;
                        }
                    }
                    //判断负环，一条路径最多经过n个节点，若存在一条路径超过n个节点，则必然存在负环
                    Deque<Integer> stack = new LinkedList<>();
                    stack.add(i);
                    while (path[stack.peek()] != stack.peek() && stack.size() < vex_num) {
                        stack.push(path[stack.peek()]);
                    }
                    if (stack.size() == vex_num) {
                        System.out.print("存在负环，程序结束\n");
                        return;
                    }
                }
            }
        }
        outPath(dis, path, k);

    }

    private void outPath(int[] dis, int[] path, int k) {
        for (int i = 0; i < vex_num; i++) {
            Deque<Integer> stack = new LinkedList<>();
            stack.add(i);
            while (path[stack.peek()] != stack.peek()) {
                stack.push(path[stack.peek()]);
            }
            System.out.printf("距离为: %d, %s->%s : ", dis[i], vex[k], vex[i]);
            System.out.printf("%s", vex[stack.pop()]);
            while (!stack.isEmpty()) {
                System.out.printf(" -> %s", vex[stack.pop()]);
            }
            System.out.println();
        }
    }


    // 关键路径


    // 判断回路

    // 判断连通

    // 求连通分量


    public static void main(String[] args) {
//        int[][] edge = new int[][]{
//                {0, 1, 0, 0, 0},
//                {1, 0, 0, 1, 0},
//                {0, 1, 0, 0, 0},
//                {1, 0, 1, 0, 0},
//        };
//        String[] s = new String[]{"A", "B", "C", "D"};
//        MGraph mGraph = new MGraph(s, edge);
//        mGraph.DFSTraverse(2);
//        mGraph.BFSTraverse(2);
        String[][] edges = new String[][]{
                {"a", "b", "1"},
                {"a", "h", "1"},
                {"a", "e", "1"},
                {"b", "c", "1"},
                {"b", "d", "1"},
                {"c", "d", "1"},
                {"c", "h", "1"},
                {"e", "f", "1"},
                {"e", "g", "1"},
        };

        MGraph mGraph = new MGraph(edges, false);
        mGraph.BFSTraverse("h");
//        mGraph.Prim(0);

        //MST
        String[][] edges2 = new String[][]{
                {"V1", "V2", "6"},
                {"V1", "V3", "1"},
                {"V1", "V4", "5"},
                {"V2", "V3", "5"},
                {"V3", "V4", "5"},
                {"V2", "V5", "3"},
                {"V3", "V5", "6"},
                {"V3", "V6", "4"},
                {"V4", "V6", "2"},
                {"V5", "V6", "6"},
        };
        MGraph mGraph1 = new MGraph(edges2, false);
        mGraph1.Prim(0);
        mGraph1.Kruskal();
        mGraph1.Dijkstra(0);

        //
//        String[][] edges3 = new String[][]{
//                {"1", "2", "10"},
//                {"1", "5", "5"},
//                {"2", "3", "1"},
//                {"2", "5", "2"},
//                {"3", "4", "4"},
//                {"4", "1", "7"},
//                {"4", "3", "6"},
//                {"5", "2", "3"},
//                {"5", "3", "9"},
//                {"5", "4", "2"},
//        };        //
        String[][] edges3 = new String[][]{
                {"1", "2", "1"},
                {"2", "3", "1"},
                {"3", "1", "-3"},
        };
        MGraph mGraph2 = new MGraph(edges3, true);
        System.out.print("Dijkstra\n");
        mGraph2.Dijkstra(0);
//        System.out.println("弗洛伊德");
//        mGraph2.Floyd();
        System.out.print("bellman ford\n");
        mGraph2.bellmanFord(0);
        System.out.print("SPFA\n");
        mGraph2.SPFA(0);
        String[][] edges4 = new String[][]{
                {"1", "2", "1"},
                {"1", "4", "1"},
                {"2", "3", "1"},
                {"2", "4", "1"},
                {"3", "5", "1"},
                {"4", "5", "1"},
                {"4", "3", "1"},
        };
        MGraph mGraph4 = new MGraph(edges4, true);
        mGraph4.topologicalSort();

        String[][] edges5 = new String[][]{
                {"带书", "出门", "1"},
                {"带电脑", "出门", "1"},
                {"出门", "吃早餐", "1"},
                {"出门", "图书馆", "1"},
                {"吃饭", "图书馆", "1"},
                {"图书馆", "回宿舍", "1"},
        };
        MGraph mGraph5 = new MGraph(edges5, true);
        mGraph5.topologicalSort();
    }


}
